#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
字符串相似度计算工具
用于计算两个字符串之间的相似度，主要用于目录名称比较
"""

import os
import re
import logging
from typing import Dict
import difflib
import math

logger = logging.getLogger(__name__)

# 性能优化：使用缓存存储已计算过的相似度结果
_similarity_cache = {}
CACHE_SIZE = 10000  # 缓存最大容量

# 预处理正则表达式的预编译
PARENTHESES_PATTERN = re.compile(r'\([^)]*\)|\[[^\]]*\]')
VERSION_PATTERN = re.compile(r'v?\d+\.\d+(\.\d+)?')
SPECIAL_CHARS_PATTERN = re.compile(r'[_\-\s]+')


def calculate_edit_distance(str1: str, str2: str) -> int:
    """
    计算两个字符串之间的编辑距离（Levenshtein Distance）
    使用优化的算法实现，比标准DP实现更快
    
    Args:
        str1: 第一个字符串
        str2: 第二个字符串
        
    Returns:
        int: 编辑距离
    """
    # 优化1：如果有一个字符串为空，直接返回另一个字符串的长度
    if not str1:
        return len(str2)
    if not str2:
        return len(str1)
    
    # 优化2：如果长度差异超过阈值，直接返回较长的长度
    # 对于相似度要求高的场景，这可以快速过滤掉明显不相似的字符串
    max_len = max(len(str1), len(str2))
    if abs(len(str1) - len(str2)) > max_len * 0.1:  # 长度差异超过10%
        return max_len
    
    # 优化3：如果两个字符串相同，直接返回0
    if str1 == str2:
        return 0
    
    # 优化4：使用difflib库的快速实现
    # difflib.SequenceMatcher在CPython中是C实现的，性能更好
    matcher = difflib.SequenceMatcher(None, str1, str2)
    # 计算编辑距离 = 总长度 - 匹配长度 * 2
    distance = len(str1) + len(str2) - 2 * matcher.find_longest_match(0, len(str1), 0, len(str2)).size
    
    return distance


def calculate_similarity_percentage(str1: str, str2: str, case_sensitive: bool = False) -> float:
    """
    计算两个字符串的相似度百分比
    
    Args:
        str1: 第一个字符串
        str2: 第二个字符串
        case_sensitive: 是否区分大小写，默认不区分
        
    Returns:
        float: 相似度百分比 (0-100)
    """
    if not case_sensitive:
        str1 = str1.lower()
        str2 = str2.lower()
    
    # 处理空字符串情况
    if not str1 and not str2:
        return 100.0
    if not str1 or not str2:
        return 0.0
    
    # 优化5：使用缓存避免重复计算
    cache_key = tuple(sorted([str1, str2]))  # 使用排序后的元组作为键，确保顺序无关
    if cache_key in _similarity_cache:
        return _similarity_cache[cache_key]
    
    # 快速路径：如果长度相差太大，直接返回低相似度
    max_len = max(len(str1), len(str2))
    min_len = min(len(str1), len(str2))
    if min_len / max_len < 0.5:  # 长度差异超过50%
        result = 0.0
    else:
        # 仅当长度差异在合理范围内时才计算编辑距离
        distance = calculate_edit_distance(str1, str2)
        # 计算相似度百分比
        result = (1 - distance / max_len) * 100
    
    # 确保结果在0-100之间
    result = max(0.0, min(100.0, result))
    
    # 更新缓存，并在缓存过大时清理
    _similarity_cache[cache_key] = result
    if len(_similarity_cache) > CACHE_SIZE:
        # 简单的LRU策略：删除一半最旧的项（这里使用随机删除作为近似）
        import random
        keys_to_remove = random.sample(list(_similarity_cache.keys()), len(_similarity_cache) // 2)
        for key in keys_to_remove:
            del _similarity_cache[key]
    
    return result


def _preprocess_directory_name(name: str) -> str:
    """
    预处理目录名称，移除可能影响相似度计算的元素
    优化版本：使用预编译的正则表达式和更高效的处理逻辑
    
    Args:
        name: 原始目录名称
        
    Returns:
        str: 预处理后的目录名称
    """
    if not name:
        return ""
    
    # 转小写
    name = name.lower()
    
    # 移除括号及其内容（使用预编译的正则表达式）
    name = PARENTHESES_PATTERN.sub('', name)
    
    # 移除版本号信息（使用预编译的正则表达式）
    name = VERSION_PATTERN.sub('', name)
    
    # 移除多余的空格和特殊字符（使用预编译的正则表达式）
    name = SPECIAL_CHARS_PATTERN.sub(' ', name).strip()
    
    return name


def calculate_directory_name_similarity(dir1: str, dir2: str) -> float:
    """
    计算两个目录名称的相似度
    专门用于目录名称比较，包含一些预处理逻辑
    
    Args:
        dir1: 第一个目录名称
        dir2: 第二个目录名称
        
    Returns:
        float: 相似度百分比 (0-100)
    """
    # 提取目录的基本名称（去除路径）
    name1 = os.path.basename(dir1.strip())
    name2 = os.path.basename(dir2.strip())
    
    # 预处理目录名称
    processed_name1 = _preprocess_directory_name(name1)
    processed_name2 = _preprocess_directory_name(name2)
    
    # 优化6：预处理后如果有一个为空，使用原始名称
    if not processed_name1:
        processed_name1 = name1.lower()  # 保持一致性，转为小写
    if not processed_name2:
        processed_name2 = name2.lower()
    
    # 计算相似度
    similarity = calculate_similarity_percentage(processed_name1, processed_name2, case_sensitive=False)
    
    logger.debug(f"目录相似度计算: '{name1}' vs '{name2}' -> {similarity:.2f}%")
    return similarity


def is_similar_by_threshold(str1: str, str2: str, threshold: float = 95.0) -> bool:
    """
    根据阈值判断两个字符串是否相似
    
    Args:
        str1: 第一个字符串
        str2: 第二个字符串
        threshold: 相似度阈值 (0-100)
        
    Returns:
        bool: 是否相似
    """
    similarity = calculate_directory_name_similarity(str1, str2)
    return similarity >= threshold


def clear_similarity_cache():
    """
    清除相似度缓存
    在处理大量数据后调用，避免内存占用过高
    """
    global _similarity_cache
    _similarity_cache.clear()


if __name__ == '__main__':
    # 测试代码
    test_pairs = [
        ("Documents", "Documents"),
        ("Music Files", "Music_Files"),
        ("Video [HD]", "Video"),
        ("Photos v2.0", "Photos"),
        ("项目文档", "项目文档备份"),
        ("Program Files", "Program Files (x86)"),
    ]
    
    print("字符串相似度测试:")
    for str1, str2 in test_pairs:
        similarity = calculate_directory_name_similarity(str1, str2)
        print(f"'{str1}' vs '{str2}': {similarity:.2f}%")
        
        for threshold in [95, 90, 85, 80]:
            is_similar = is_similar_by_threshold(str1, str2, threshold)
            print(f"  阈值{threshold}%: {'相似' if is_similar else '不相似'}")
        print()